package heap;

import java.util.Arrays;
import java.util.Comparator;

class LessIntComp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
}
class GreaterIntComp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
// 假设：创建的是小堆----泛型实现
public class MyPriorityQueue<E> {
    private Object[] hp;
    private int size = 0;
    private Comparator<? super E> comparator = null;

    // java8中：优先级队列的默认容量是11
    public MyPriorityQueue(Comparator<? super E> com) {
        hp = new Object[11];
        size = 0;
        comparator = com;
    }

    public MyPriorityQueue() {
        hp = new Object[11];
        size = 0;
        comparator = null;
    }

    // 按照指定容量设置大小
    public MyPriorityQueue(int capacity) {
        capacity = capacity < 1 ? 11 : capacity;
        hp = new Object[capacity];
        size = 0;
    }

    // 注意：没有此接口，给学生强调清楚
    // java8中：可以将一个集合中的元素直接放到优先级队列中
    public MyPriorityQueue(E[] array) {
        // 将数组中的元素放到优先级队列底层的容器中
        hp = Arrays.copyOf(array, array.length);
        size = hp.length;
        // 对hp中的元素进行调整
        // 找到倒数第一个非叶子节点
        for (int root = ((size - 2) >> 1); root >= 0; root--) {
            shiftDown(root);
        }
    }

    // 插入元素
    public void offer(E val) {
        // 先检测是否需要扩容
        grow();
        // 将元素放在最后位置，然后向上调整
        hp[size] = val;
        size++;
        shiftUp(size - 1);
    }

    // 删除元素: 删除堆顶元素
    public void poll() {
        if (isEmpty()) {
            return;
        }
        // 将堆顶元素与堆中最后一个元素进行交换
        swap((E[]) hp, 0, size - 1);
        // 删除最后一个元素
        size--;
        // 将堆顶元素向下调整
        shiftDown(0);
    }

    public int size() {
        return size;
    }

    public E peek() {
        return (E) hp[0];
    }

    boolean isEmpty() {
        return 0 == size;
    }

    // 向下调整
    private void shiftDown(int parent) {
        if (null == comparator) {
            shiftDownWithcompareTo(parent);
        } else {
            shiftDownWithComparetor(parent);
        }
    }

    // 使用比较器比较
    private void shiftDownWithComparetor(int parent) {
        // child作用：标记最小的孩子
        // 因为堆是一个完全二叉树，而完全二叉树可能有左没有有
        // 因此：默认情况下，让child标记左孩子
        int child = parent * 2 + 1;
        // while循环条件可以一直保证parent左孩子存在，但是不能保证parent的右孩子存在
        while (child < size) {
        // 找parent的两个孩子中最小的孩子，用child进行标记
        // 注意：parent的右孩子可能不存在
        // 调用比较器来进行比较
            if (child + 1 < size && comparator.compare((E) hp[child + 1], (E) hp[child]) < 0) {
                child += 1;
            }
        // 如果双亲比较小的孩子还大，将双亲与较小的孩子交换
            if (comparator.compare((E) hp[child], (E) hp[parent]) < 0) {
                swap((E[]) hp, child, parent);
        // 小的元素往下移动，可能导致parent的子树不满足堆的性质
        // 因此：需要继续向下调整
                parent = child;
                child = child * 2 + 1;
            } else {
                return;
            }
        }
    }

    // 使用compareTo比较
    private void shiftDownWithcompareTo(int parent) {
        // child作用：标记最小的孩子
        // 因为堆是一个完全二叉树，而完全二叉树可能有左没有有
        // 因此：默认情况下，让child标记左孩子
        int child = parent * 2 + 1;
        // while循环条件可以一直保证parent左孩子存在，但是不能保证parent的右孩子存在
        while (child < size) {
        // 找parent的两个孩子中最小的孩子，用child进行标记
        // 注意：parent的右孩子可能不存在
        // 向上转型，因为E的对象都实现了Comparable接口
            if (child + 1 < size && ((Comparable<? super E>) hp[child]).compareTo((E) hp[child]) < 0) {
                child += 1;
            }
        // 如果双亲比较小的孩子还大，将双亲与较小的孩子交换
            if (((Comparable<? super E>) hp[child]).compareTo((E) hp[parent]) < 0) {
                swap((E[]) hp, child, parent);
        // 小的元素往下移动，可能导致parent的子树不满足堆的性质
        // 因此：需要继续向下调整
                parent = child;
                child = child * 2 + 1;
            } else {
                return;
            }
        }
    }

    // 向上调整
    void shiftUp(int child) {
        if (null == comparator) {
            shiftUpWithCompareTo(child);
        } else {
            shiftUpWithComparetor(child);
        }
    }

    void shiftUpWithComparetor(int child) {
        // 获取孩子节点的双亲
        int parent = ((child - 1) >> 1);
        while (0 != child) {
        // 如果孩子比双亲还小，则不满足小堆的性质，交换
            if (comparator.compare((E) hp[child], (E) hp[parent]) < 0) {
                swap((E[]) hp, child, parent);
                child = parent;
                parent = ((child - 1) >> 1);
            } else {
                return;
            }
        }
    }

    void shiftUpWithCompareTo(int child) {
        // 获取孩子节点的双亲
        int parent = ((child - 1) >> 1);
        while (0 != child) {
        // 如果孩子比双亲还小，则不满足小堆的性质，交换
            if (((Comparable<? super E>) hp[child]).compareTo((E) hp[parent]) < 0) {
                swap((E[]) hp, child, parent);
                child = parent;
                parent = ((child - 1) >> 1);
            } else {
                return;
            }
        }
    }

    void swap(E[] hp, int i, int j) {
        E temp = hp[i];
        hp[i] = hp[j];
        hp[j] = temp;
    }

        // 仿照JDK8中的扩容方式，注意还是有点点的区别，具体可以参考源代码
    void grow() {
        int oldCapacity = hp.length;
        if (size() >= oldCapacity) {
        // Double size if small; else grow by 50%
            int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                    (oldCapacity + 2) :
                    (oldCapacity >> 1));
            hp = Arrays.copyOf(hp, newCapacity);
        }
    }
    public static void main(String[] args) {
        int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};
        // 小堆---采用比较器创建小堆
        MyPriorityQueue<Integer> mq1 = new MyPriorityQueue(new LessIntComp());
        for (int e : arr) {
            mq1.offer(e);
        }
        // 大堆---采用比较器创建大堆
        MyPriorityQueue<Integer> mq2 = new MyPriorityQueue(new GreaterIntComp());
        for (int e : arr) {
            mq2.offer(e);
        }
        // 小堆--采用CompareTo比较创建小堆
        MyPriorityQueue<Integer> mq3 = new MyPriorityQueue();
        for (int e : arr) {
            mq3.offer(e);
        }
    }
}
